You are to write (in C, C++ or Java) a program that simulates a simple cache. The parameters associated with the...
krynalswamzYou are to write (in C, C++ or Java) a program that simulates a simple cache. The parameters
associated with the memory system are as follows:
• Memory Block Size = Cache Line Size = 16
• Number of Blocks in Memory =16
• Number of Cache Lines = 8
• Write Through Cache Policy
Each line of the cache has the following components:
Valid
Bit
0 =
The set
number
Empty
1 =
cache
Valid
belongs
Set Tag Data Values
Block
Number
this
Memory
line
Block
Copy
to
Byte
0
of
Byte
Byte
1
... Byte
2
7
Your memory should be initialized to zeros at the start of your program.
You have any two choice of which type of block placement strategy to implement for your project from
below three:
• Direct mapped
• 2-way set associative
• Fully associative
Your submission must include complete instructions for compiling and executing your
code.
Your program should have the following functions:
void print_cache(cache_line_t *my_cache)
This function prints all current contents of cache. For example:
=================== CACHE ==========================
Set = 0 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Set = 0 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Set = 1 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Set = 1 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Set = 2 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Set = 2 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Set = 3 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Set = 3 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1
void print_mem(int num_cache_lines, int cache_line_size)
This function prints all current contents of memory. For example:
================================== MEM ==========================
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
30 31 32 234 34 35 36 37 38 39 40 41 42 43 44 45
40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
50 51 52 53 54 55 56 57 58 59 60 61 62 66 64 65
60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75
70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85
80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95
90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105
100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115
110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125
120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135
130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145
140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155
150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165
void init_cache(cache_line_t my_cache[], int associativity)
This function initializes the cache to the following state:
============================== CACHE ============================
Set = 0 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Set = 0 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Set = 1 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Set = 1 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Set = 2 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Set = 2 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Set = 3 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Set = 3 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165
int map_mem_block_to_cacheline_for_replacement(int block_num, int associativity, cache_line_t
my_cache[])
This function receives the memory block number of interest and calculates the cache line number
associated with is using the formula for 2-Way Set Associative caches. Please note that internal to this
function, you determine the SET NUMBER of the interest. Then within that set you search for the first
cache line whose valid bit is 0. This cache line number then will be returned by this function.
If no cache lines with valid bit equal to 0 were found, then randomly select one of the cache
lines to be replaced.
void write_to_cache(int block_num, int offset, int value, cache_line_t my_cache[], int
associativity)
This function writes a single value to an offset within a given block number
2
void load_from_mem(int block_num, int block_size, cache_line_t my_cache[], int associativity)
This function loads a block from memory (identified by the block number into the
appropriate cache line (as per the Set associative cache formula). It also sets the valid bit for
this cache line to 1, and copies the block number of the memory into the tag field.
void write_through_to_mem(int block_num, int block_size, int associativity, cache_line_t
my_cache[])
This function writes an entire cache line to the appropriate block in the memory associated
with it.
int is_cache_hit(int block_num, int associativity, cache_line_t my_cache[])
Gets a mem block number and determines if that block is already in cachememory block
number has its tag equal to the block number
int calc_number_of_sets(int associativity)
This function calculates the number of sets in this cache based on the associativity given.
int calc_my_set_number(int cache_line_num, int num_lines, int associativity)
this function calculates the set number that any cache line belongs to
int map_mem_block_to_set(int block_num, int associativity) ss based on associativity
returns the set number in cache mapped to a mem block number
void store_to_mem(int block_num, int offset, int value)
Stores a single value to the given offset of a given block in memory
3
The main program should have the following flow:
init_cache
init mem
while true
{
Print the number of hits and
misses print_mem print_cache
Get from the keyboard the command from the CPU on the bus:
If the command is READ, get the block number, and offset.
Then if ( is_cache_hit)
increment num_read_hits counter
else
increment num_read_misses counter
load_from_mem
print the value of the memory location requested
If the command is WRITE, get the block number, offset, and value.
Then if ( is_cache_hit)
increment num_write_hits counter
write_to_cache
write_thru_to_mem
else
increment num_write_misses counter
load_from_mem
print the value of the memory location written
if the command is QUIT, exit the loop
}
4
A sample run of the program is shown below for your reference and understanding:
$ ./cache.exe 2
2-way Set Associative Map Cache...
Set Associativity of this cache: 2
Number of sets in this cache: 4
=============== cache performance
=============== read misses = 0
read hits = 0 write misses = 0
write hits = 0
================================== MEM ==========================
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75
70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85
80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95
90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105
100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115
110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125
120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135
130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145
140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155
150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165
============================== CACHE ============================
Set = 0 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0
Set = 0 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0
0 Set = 1 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0
0 0 Set = 1 v = 0 tag = -99 0 0 0 0 0 0 0 0 0
0 0 0
Set = 2 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0
0 Set = 2 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0
0 0 Set = 3 v = 0 tag = -99 0 0 0 0 0 0 0 0 0
0 0 0
Set = 3 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0
5
Enter choice:
[0] to read from mem
[1] to write to mem
[2] to quit
--
> 0
enter block number: 3
enter offset: 2
get_cpu_action(): action = READ, block = 3, offset =
2 cache read miss block [3] offset[2] --> [0]
=============== cache performance ===============
read misses = 1 read hits = 0
write misses = 0 write hits = 0
================================== MEM ==========================
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75
70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85
80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95
90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105
100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115
110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125
120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135
130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145
140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155
150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165
============================== CACHE ============================
Set = 0 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0
Set = 0 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0
Set = 1 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0
Set = 1 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0
Set = 2 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0
Set = 2 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0
Set = 3 v = 1 tag = 3 30 31 32 33 34 35 36 37 38 39 40 41 4
Set = 3 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0
6
Enter choice:
[0] to read from mem
[1] to write to mem
[2] to quit
--
> 0
enter block number: 5
enter offset: 1
get_cpu_action(): action = READ, block = 5, offset =
1 cache read miss block [5] offset[1] --> [0]
=============== cache performance ===============
read misses = 2 read hits = 0
write misses = 0 write hits = 0
================================== MEM ==========================
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75
70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85
80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95
90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105
100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115
110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125
120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135
130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145
140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155
150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165
============================== CACHE============================
Set = 0 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0
Set = 0 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0
Set = 1 v = 1 tag = 5 50 51 52 53 54 55 56 57 58 59 60 61 6
Set = 1 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0
Set = 2 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0
Set = 2 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0
Set = 3 v = 1 tag = 3 30 31 32 33 34 35 36 37 38 39 40 41 4
Set = 3 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0
7
Enter choice:
[0] to read from mem
[1] to write to mem
[2] to quit
--
> 1
enter block number: 4
enter offset: 1
enter value: 444
get_cpu_action(): action = WRITE, block = 4, offset = 1 value =
444 cache write miss block [4] offset[1] --> [0] ===============
cache performance =============== read misses = 2
read hits = 0 write misses = 1 write hits
= 0
================================== MEM ==========================
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
40 444 42 43 44 45 46 47 48 49 50 51 52 53 54 55
50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 70
71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 80 81
82 83 84 85 86 87 88 89 90 91 92 93 94 95
90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105
100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115
110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125
120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135
130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145
140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155
150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165
============================== CACHE ============================
Set = 0 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0
Set = 0 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0
Set = 1 v = 1 tag = 5 50 51 52 53 54 55 56 57 58 59 60 61 6
Set = 1 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0
Set = 2 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0
Set = 2 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0
Set = 3 v = 1 tag = 3 30 31 32 33 34 35 36 37 38 39 40 41
Set = 3 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0
8
Enter choice:
[0] to read from mem
[1] to write to mem
[2] to quit
--
> 0
enter block number: 4
enter offset: 1
get_cpu_action(): action = READ, block = 4, offset =
1 cache read miss block [4] offset[1] --> [0]
=============== cache performance ===============
read misses = 3 read hits = 0
write misses = 1 write hits = 0
================================== MEM ==========================
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 10
11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
40 444 42 43 44 45 46 47 48 49 50 51 52 53 54 55
50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75
70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85
80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95
90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105
100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115
110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125
120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135
130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145
140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155
150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165
============================== CACHE ============================
Set = 0 v = 1 tag = 4 40 444 42 43 44 45 46 47 48 49 50 51 5
Set = 0 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0
Set = 1 v = 1 tag = 5 50 51 52 53 54 55 56 57 58 59 60 61 6
Set = 1 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0
Set = 2 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0
Set = 2 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0
Set = 3 v = 1 tag = 3 30 31 32 33 34 35 36 37 38 39 40 41 4
Set = 3 v = 0 tag = -99 0 0 0 0 0 0 0 0 0 0 0 0
9
Enter choice:
[0] to read from mem
[1] to write to mem
[2] to quit
--
> q
exiting main
loop
*******************************************************************************************
10 years ago
10
